#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <emmintrin.h>
#include <pthread.h>
#include <errno.h>
#include <semaphore.h>

// Random /////////////////////////////////////////////////////////////////////

#include <limits.h>
#include <stddef.h>

#define TYPE_0          0
#define BREAK_0         8
#define DEG_0           0
#define SEP_0           0
#define TYPE_1          1
#define BREAK_1         32
#define DEG_1           7
#define SEP_1           3
#define TYPE_2          2
#define BREAK_2         64
#define DEG_2           15
#define SEP_2           1
#define TYPE_3          3
#define BREAK_3         128
#define DEG_3           31
#define SEP_3           3
#define TYPE_4          4
#define BREAK_4         256
#define DEG_4           63
#define SEP_4           1
#define MAX_TYPES       5       /* Max number of types above.  */

static int32_t randtbl[DEG_3 + 1] =
  {
    TYPE_3,
    -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
    1627687941, -179304937, -2073333483, 1780058412, -1989503057,
    -615974602, 344556628, 939512070, -1249116260, 1507946756,
    -812545463, 154635395, 1388815473, -1926676823, 525320961,
    -1009028674, 968117788, -123449607, 1284210865, 435012392,
    -2017506339, -911064859, -370259173, 1132637927, 1398500161,
    -205601318,
  };

static int32_t *fptr = &randtbl[SEP_3 + 1];
static int32_t *rptr = &randtbl[1];
static int32_t *state = &randtbl[1];
static int32_t *end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])];

unsigned int cp_random ()
{
    int32_t retval;
    int32_t val;

    val = *fptr += *rptr;
    retval = (val >> 1) & 0x7fffffff;
    ++fptr;
    if (fptr >= end_ptr) {
        fptr = state;
        ++rptr;
    }
    else {
        ++rptr;
        if (rptr >= end_ptr)
            rptr = state;
    }
    return retval;
}

// Sort ///////////////////////////////////////////////////////////////////////

typedef struct {
    int *v;
    int n;
} pstruct;

#define BB 8
#define NB (1<<BB)
#define BT 7
#define NT (1<<BT)

sem_t limit;

void radixsort(void* params)
{
    pstruct *rparams = (pstruct*) params;
    unsigned int *v = rparams->v;
    unsigned int n = rparams->n;
    unsigned int *aux = (unsigned int*) malloc(n*sizeof(int));
    unsigned int *bucket = (unsigned int*) malloc(NB*sizeof(int));
    unsigned char c[4];
    unsigned int* cp = (int*) c;
    int i;

    sem_wait(&limit);

    memset(bucket, 0, NB*sizeof(int));

    for (i = 0; i < n; i++) {
        *cp = v[i];
        bucket[c[0]]++;
    }
    for (i = 1; i < NB; i++) {
        bucket[i] += bucket[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        *cp = v[i];
        aux[--bucket[c[0]]] = v[i];
    }

    memset(bucket, 0, NB*sizeof(int));

    for (i = 0; i < n; i++) {
        *cp = aux[i];
        bucket[c[1]]++;
    }
    for (i = 1; i < NB; i++) {
        bucket[i] += bucket[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        *cp = aux[i];
        v[--bucket[c[1]]] = aux[i];
    }

    memset(bucket, 0, NB*sizeof(int));

    for (i = 0; i < n; i++) {
        *cp = v[i];
        bucket[c[2]]++;
    }
    for (i = 1; i < NB; i++) {
        bucket[i] += bucket[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        *cp = v[i];
        aux[--bucket[c[2]]] = v[i];
    }

    sem_post(&limit);

    rparams->v = aux;
}

int main(int argc, char *argv[])
{
    unsigned int seed, n, i, r;
    pstruct *p, ps[NT];
    pthread_t *t, th[NT];

    if (scanf("%d %d", &n, &seed) != 2) {
        fprintf(stderr, "parametres\n");
        exit(0);
    }

    srand(seed);

    for (i = 0; i < NT; i++) {
        p = &ps[i];
        p->v = (unsigned int*) malloc((n/NT*10/9)*sizeof(int));
        p->n = 0;
    }

    for (i = 0; i < n; i++) {
        r = cp_random();
        p = &ps[(r>>(31-BT)) % (1<<BT)];
        p->v[p->n] = r;
        p->n++;
    }

    sem_init(&limit, 0, 2);

    for (i = 0; i < NT; i++) {
        pthread_create(&th[i], NULL, radixsort, &ps[i]);
    }

    for (i = 0; i < NT; i++) {
        p = &ps[i];
        pthread_join(th[i], NULL);
        write(1, p->v, p->n*sizeof(int));
    }

    sem_destroy(&limit);

    exit(0);
}
